//给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。 
//
// 返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
// 
//
// 示例 1： 
//
// 
//输入：array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
//输出：[1, 3]
// 
//
// 示例 2： 
//
// 
//输入：array1 = [1, 2, 3], array2 = [4, 5, 6]
//输出：[] 
//
// 提示： 
//
// 
// 1 <= array1.length, array2.length <= 100000 
// 
//
// Related Topics 数组 哈希表 二分查找 排序 👍 54 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author ldltd
 * @date 2025-09-10 23:36:11
 * @description 面试题 16.21.交换和
 */
public class SumSwapLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SumSwapLcci fun=new SumSwapLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] findSwapValues2(int[] array1, int[] array2) {
		Arrays.sort(array1);
		Arrays.sort(array2);
		int sum1 = Arrays.stream(array1).sum();
		int sum2 = Arrays.stream(array2).sum();
		// sum1-a+b=sum2-b+a -> sum1+2b=sum2+2a sum1-sum2=2a-2b
		int diff = sum1 - sum2;

		// 如果差值是奇数，无法通过交换得到相等和
		if (diff % 2 != 0) {
			return new int[]{};
		}
		int i = 0, j = 0;
		while (i < array1.length && j < array2.length) {
			long currentDiff = (long) array1[i] - array2[j];
			long targetDiff = diff / 2; // 这里除法是安全的，因为前面检查过是偶数
			if (currentDiff == targetDiff) {
				return new int[]{array1[i], array2[j]};
			} else if (currentDiff < targetDiff) {
				i++;
			} else {
				j++;
			}
		}

		return new int[]{};
	}
	// 二分
	public int[] findSwapValues1(int[] array1, int[] array2) {
		Arrays.sort(array1);
		Arrays.sort(array2);
		int sum1 = Arrays.stream(array1).sum();
		int sum2 = Arrays.stream(array2).sum();

		// sum1 - a + b = sum2 - b + a => sum1 - sum2 = 2(a - b)
		int diff = sum1 - sum2;

		// 避免除法，直接使用 diff = 2(a - b) 的关系
		// 我们需要找到 a - b = diff / 2，但由于避免除法，我们可以：
		// 如果 diff 是奇数，直接返回（因为 2(a-b) 必须是偶数）
		if (diff % 2 != 0) {
			return new int[]{};
		}

		// 仍然使用 target = diff / 2，但这是整数除法，不会有精度问题
		// 因为前面已经检查过 diff % 2 == 0
		int target = diff / 2;

		int i = 0, j = 0;
		while (i < array1.length && j < array2.length) {
			int currentDiff = array1[i] - array2[j];

			if (currentDiff == target) {
				return new int[]{array1[i], array2[j]};
			} else if (currentDiff < target) {
				i++;
			} else {
				j++;
			}
		}

		return new int[]{};
	}
	//哈希
	public int[] findSwapValues(int[] array1, int[] array2) {
		int sum1 = 0, sum2 = 0;
		int[] small, big;
		if (array1.length < array2.length) {
			small = array1;
			big = array2;
		} else {
			small = array2;
			big = array1;
		}
		HashSet<Integer> set = new HashSet<>();
		for (int n : small) {
			sum1 += n;
		}
		for (int n : big) {
			sum2 += n;
			set.add(n << 1);
		}
		for (int n : small) {
			int target = sum2 - sum1 + 2 * n;
			if (set.contains(target)) {
				if (array1.length < array2.length) {
					return new int[]{n, target >> 1};
				} else {
					return new int[]{target >> 1, n};
				}
			}
		}
		return new int[0];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
